#include <stdio.h>
#include <stdlib.h>

// 哈夫曼树节点结构体定义
// 哈夫曼树是一种带权路径长度最短的二叉树，用于数据压缩等场景
typedef struct HuffmanNode {
    int weight;               // 节点的权值（用于计算合并优先级）
    int parent;               // 父节点的索引（-1表示无父节点）
    int leftChild;            // 左孩子的索引（-1表示无左孩子）
    int rightChild;           // 右孩子的索引（-1表示无右孩子）
    // 采用索引而非指针存储关系，更适合用数组管理所有节点
} HuffmanNode;

/**
 * 构造哈夫曼树
 * 原理：每次从当前节点中选择两个权值最小的节点，合并为一个新节点，
 *       新节点权值为两个子节点权值之和，重复此过程直到只剩一个节点
 * 
 * @param weights 权值数组（初始叶子节点的权值）
 * @param n 权值的个数（初始叶子节点的数量）
 * @return 构建好的哈夫曼树节点数组（共2n-1个节点）
 */
HuffmanNode* createHuffmanTree(int* weights, int n) {
    // 边界检查：权值数量不能小于1
    if (n <= 0) {
        printf("权值数量必须大于0\n");
        return NULL;
    }
    
    // 哈夫曼树的总节点数 = 初始叶子节点数 + 合并产生的非叶子节点数
    // 合并n个叶子节点需要n-1次合并，产生n-1个非叶子节点，因此总节点数为2n-1
    int totalNodes = 2 * n - 1;
    
    // 分配存储所有节点的数组空间
    HuffmanNode* huffTree = (HuffmanNode*)malloc(totalNodes * sizeof(HuffmanNode));
    if (huffTree == NULL) {
        printf("内存分配失败，无法创建哈夫曼树\n");
        return NULL;
    }
    
    // 初始化叶子节点（前n个节点为叶子节点）
    for (int i = 0; i < n; i++) {
        huffTree[i].weight = weights[i];  // 叶子节点权值为输入的权重
        huffTree[i].parent = -1;          // 初始无父节点
        huffTree[i].leftChild = -1;       // 叶子节点无左孩子
        huffTree[i].rightChild = -1;      // 叶子节点无右孩子
    }
    
    // 初始化非叶子节点（后n-1个节点为合并产生的非叶子节点）
    for (int i = n; i < totalNodes; i++) {
        huffTree[i].weight = 0;           // 权值后续会计算（子节点权值之和）
        huffTree[i].parent = -1;          // 初始无父节点
        huffTree[i].leftChild = -1;       // 初始无左孩子
        huffTree[i].rightChild = -1;      // 初始无右孩子
    }
    
    // 构建哈夫曼树的核心循环：共需要n-1次合并（产生n-1个非叶子节点）
    for (int i = n; i < totalNodes; i++) {
        // 查找当前未被合并（无父节点）的两个权值最小的节点
        int min1 = -1;  // 存储第一个最小权值节点的索引
        int min2 = -1;  // 存储第二个最小权值节点的索引
        
        // 遍历所有已初始化的节点（0到i-1），寻找两个最小节点
        for (int j = 0; j < i; j++) {
            // 只考虑未被合并的节点（parent == -1）
            if (huffTree[j].parent == -1) {
                // 第一次找到未合并节点，直接赋值给min1
                if (min1 == -1) {
                    min1 = j;
                } 
                // 第二次找到未合并节点，赋值给min2
                else if (min2 == -1) {
                    min2 = j;
                } 
                // 后续找到的节点，需要比较权值大小并更新min1和min2
                else {
                    // 当前节点权值比min1小，更新min2为原来的min1，min1为当前节点
                    if (huffTree[j].weight < huffTree[min1].weight) {
                        min2 = min1;
                        min1 = j;
                    } 
                    // 当前节点权值介于min1和min2之间，更新min2
                    else if (huffTree[j].weight < huffTree[min2].weight) {
                        min2 = j;
                    }
                }
            }
        }
        
        // 将找到的两个最小节点合并为一个新节点（当前i对应的节点）
        huffTree[min1].parent = i;       // 第一个最小节点的父节点设为当前节点
        huffTree[min2].parent = i;       // 第二个最小节点的父节点设为当前节点
        huffTree[i].leftChild = min1;    // 当前节点的左孩子为第一个最小节点
        huffTree[i].rightChild = min2;   // 当前节点的右孩子为第二个最小节点
        huffTree[i].weight = huffTree[min1].weight + huffTree[min2].weight;  // 新节点权值为两者之和
    }
    
    return huffTree;
}

/**
 * 前序遍历打印哈夫曼树（根->左->右）
 * 用于直观展示树的结构，通过缩进表示节点的深度
 * 
 * @param huffTree 哈夫曼树节点数组
 * @param index 当前遍历的节点索引
 * @param depth 当前节点的深度（用于控制缩进）
 */
void preOrderTraversal(HuffmanNode* huffTree, int index, int depth) {
    // 递归终止条件：树为空或节点索引无效（-1）
    if (huffTree == NULL || index == -1) {
        return;
    }
    
    // 打印当前节点：根据深度缩进，显示权值和索引
    for (int i = 0; i < depth; i++) {
        printf("  ");  // 每个深度缩进两个空格
    }
    printf("权值: %d (索引: %d)\n", huffTree[index].weight, index);
    
    // 递归遍历左子树（深度+1）
    preOrderTraversal(huffTree, huffTree[index].leftChild, depth + 1);
    
    // 递归遍历右子树（深度+1）
    preOrderTraversal(huffTree, huffTree[index].rightChild, depth + 1);
}

int main() {
    // 示例：待编码的字符出现频率（权值）
    // 实际应用中，权值通常代表字符出现的次数或概率
    int weights[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(weights) / sizeof(weights[0]);  // 计算权值的个数（6个）
    
    // 创建哈夫曼树
    HuffmanNode* huffTree = createHuffmanTree(weights, n);
    if (huffTree == NULL) {
        return 1;  // 创建失败则退出程序
    }
    
    // 打印哈夫曼树结构（前序遍历）
    // 哈夫曼树的根节点索引为总节点数-1 = (2n-1)-1 = 2n-2
    printf("哈夫曼树结构（前序遍历，缩进表示深度）：\n");
    preOrderTraversal(huffTree, 2 * n - 2, 0);
    
    // 释放动态分配的内存，避免内存泄漏
    free(huffTree);
    
    return 0;
}
